Built-in self-test (BIST) is emerging as an attractive alternative to conventional methods of testing microelectronics devices at time of manufacture. In BIST, additional circuitry is added to a circuit-under-test to provide on-chip test-pattern generation, test-response evaluation, and test control. Consequently, BIST is significantly changing the way that integrated circuits are tested. It reduces testing cost by shortening test application time, minimizing the amount of test data that must be stored by an external tester, and reducing tester costs. Its implementation can result in a reduction of the product development cycle and a reduction in the cost of system maintenance.
The basic BIST objectives are on-chip test-pattern generation and test-response compaction. By far the most commonly-used means for generating test patterns on chip are pseudo-random test pattern generators (PRPGs). A PRPG generates a set of test patterns based on an initial value, or seed, loaded into memory elements within the PRPG. The popularity of pseudo-random tests stems from the very simple hardware required to implement the test generation. The two principal forms of PRPGs, which evolved over time and are now commonly in use, are both linear finite state machines: linear feedback shifts registers (LFSRs) and one-dimensional linear hybrid cellular automata (LHCAs).
Typically, an LFSR consists of interconnected memory elements (also referred to as flip-flops, stages, cells, etc.) and linear logic elements (such as XOR or XNOR gates). An LFSR of length n can be also represented by its characteristic polynomial hnxn+hn−1xn−1 +. . . +h0, where the term hixi refers to the ith flip-flop of the register, such that, if hi=1, then there is a feedback tap taken from this flip-flop. Also, h0=1. FIG. 1A shows a type I LFSR, or Fibonacci generator. FIG. 1B shows a type II LFSR, or Galois generator, which uses a shift register with interspersed XOR gates. If an LFSR (of either type) is initialized to a nonzero value, then it can cycle through a number of states before coming back to the initial state. A characteristic polynomial which causes an n-bit LFSR to go through all possible 2n−1 nonzero states is called a primitive characteristic polynomial. The corresponding LFSR is often referred to as a maximum-length LFSR, and the resultant output sequence is termed a maximum-length sequence or m-sequence.
An LHCA is a collection of memory cells connected in such a way that each cell is restricted to local neighborhood interactions. These relationships are expressed-by rules that determine the next state of a given cell based on information received from its neighbors. For example, if cell c can communicate only With its two neighbors, c−1 and (c+1, the so-called rules 90 and 150 are usually employed. The rule 90 can be implemented by a linear logic according to the formula xc(t+1)=xc−1(t)⊕ xc+1(t), while the rule 150 satisfies the equation xc(t+1)=xc−1(t) ⊕xc(t) ⊕ xc+1(t), where xc(t) represents the state of cell c at time t. An example of an LHCA is shown in FIG. 1C. This automaton features null boundary conditions. That is, the conditions behave as if the boundary always supplies a zero from beyond the automaton to the inputs to the exterior cells. In an alternative embodiment, the LHCA has cyclic boundary conditions in- which the inputs to the exterior cells are connected so that the automaton forms a circle. Contrary to the LHCA with null boundary conditions, the LHCA with cyclic boundary conditions is unable to produce an m-sequence.
Although LFSRs and LHCAs can generate a large set of pseudo-random test patterns from one seed, this set seldom provides sufficient fault coverage for a circuit-under-test. At best, 95-96% coverage of stuck-at faults can be achieved, even if test points are added to the circuit-under-test to address random pattern-resistant faults. If higher fault coverage is desired, the pseudo-random test patterns must be supplemented in some way. One supplementing technique is to provide from an external tester additional seeds to the PRPG that target specific faults not detected by the initial seed. Each additional seed generates a set of patterns. Each set, however takes considerable time to generate. Another supplementing technique is to provide fully specified deterministic patterns that bypass the PRPG and target directly the remaining, random pattern resistant faults. This reduces testing time, but increases memory requirements because the external tester memory required to store these “top-up” patterns is significant, often exceeding 50% of the memory required for a complete set of deterministic patterns.